package com.xx.springboot.DataStructure.Test;


/**
 * @author xiaoxiunique
 * @description 实现基于数组的循环队列
 */
public class LoopQueue<E> {

    private int size;
    private int front, tail;
    private E[] data;

    /**
     * 有参构造函数  初始化循环队列
     */
    public LoopQueue(int capacity){
        size = 0;
        front = 0;
        tail = 0;
        data = (E[]) new Object[capacity + 1];
    }

    /**
     * 无参构造函数
     */
    public LoopQueue(){
        this(10);
    }

    /**
     * 获取得到数组的长度
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 获取得到数组的空间大小
     * @return
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 判断循环队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 入队
     * @param e
     */
    public void enqueue(E e) {

        if((tail + 1) % data.length == front)
            resize(getCapacity() * 2);

        data[tail] = e;
        size ++;
        tail = (tail + 1) % data.length;
    }

    private void resize(int newCapacity) {
        E[] newArr = (E[]) new Object[newCapacity];

        for (int i = 0; i < data.length; i++)
            newArr[i] = data[(i + front) % data.length];

        front = 0;
        tail = size;
        data = newArr;
    }

    /**
     * 出队
     * @return
     */
    public E dequeue() {

        if(isEmpty())
            throw new IllegalArgumentException("队列为空");

        E res = data[front];
        front = (front + 1) % data.length;
        size --;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return res;
    }

    /**
u     * 查看队头元素
     * @return
     */
    public E getFront() {

        if(isEmpty())
            throw new IllegalArgumentException("队列为空");

        return data[front];
    }

    @Override
    public String toString() {
        StringBuffer res = new StringBuffer();

        res.append("front :");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if((i + 1) % data.length != tail)
                res.append(",");
        }

        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> list = new LoopQueue<Integer>();
        for (int i = 0; i < 10; i++) {
            list.enqueue(i);
        }
        System.out.println(list);
    }
}

